\documentclass[a4paper,notitlepage]{article}
\usepackage[utf8]{inputenc}
\usepackage[portuges,brazilian]{babel}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{paralist}
\usepackage{natbib}
\usepackage{multirow}
\usepackage{rotating}
\usepackage{indentfirst}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{listliketab}
\usepackage{wrapfig}
%\usepackage{ae}  %Talvez precisemos disso
%\usepackage[ansinew]{inputenc}

\setlength{\topmargin}{0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\textheight}{9.7in}
\setlength{\textwidth}{6.2in}
\setlength{\footskip}{0.4in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\parindent}{0.25in}
\setlength{\parskip}{-0.01in}

\begin{document}


\title{
    \includegraphics[scale=0.15]{extra/logoUnicamp.jpg} \\[0.5cm]
    \textbf{MC548 - Projeto e Análise de Algoritmos II} \\[0.2cm]
    Trabalho Prático \\
    Prof. Cid C. de Souza}

\author{Guilherme Adriano Fôlego (071033) \\ Watson Yuuma Sato (072652)}

\maketitle

%\tableofcontents


\section{Introdução}

\subsection{Objetivo}
Dada a intratabilidade dos problemas \textit{NP}-Completo, muito se trabalha para 
contornar as dificuldades em resolvê-los com eficiência.
Este trabalho foca no uso de técnicas e alternativas para se resolver um problema \textit{NP}-Completo,
assim como testar e avaliar comparativamente seu desempenho.\\

O problema \textit{NP} em questão é o \textit{flowshop scheduling} com o critério de sum-finishing-time e, para resolvê-lo, usaremos três metodologias
diferentes: \begin{inparaenum}[\itshape (i)]
    \item branch-and-bound;
    \item programação linear inteira; e
    \item heurística.
\end{inparaenum} \\

Utilizando as metodologias, implementamos três resolvedores para o problema. 
Com o algoritmo de Branch-and-Bound o desenvolvimento foi direto, ficando os detalhes mais importantes 
por conta da estrutura de dados utilizada, da escolha de um nó ativo e dos limitantes utilizados. 
No caso do método de PLI, apenas modelamos o problema, a resolução ficou por conta de um utilitário
resolvedor PLI livre e gratuito, o \textit{glpk}. 
Tratando da heurística, utilizando da intuição e experimentação desenvolvemos algumas abordagens para tratar 
do problema; as melhores foram combinadas e utilizadas como peça única na resolução. \\

Em seguida, realizamos testes com as instâncias fornecidas pelo docente, 
apresentamos uma breve análise e, por fim, as conclusões finais.

\subsection{Definicação do Problema}
O problema de sum-finishing-time está descrito em \citet[p. 444--445]{Papadimitriou82},
o qual reescrevemos a seguir.
É dado um conjunto de $n$ jobs\footnote{serviço}, \begin{math}\mathcal{J} = \{J_1,\ldots,J_n\} \end{math}, onde cada
job contém duas tasks\footnote{tarefa}, cada uma a ser processada em uma de duas máquinas.
O job $J_j$ leva um tempo de processamento $\tau_{ij}$ na máquina $i$, e cada task deve finalizar
sua execução na máquina 1 antes de iniciar na máquina 2.
Seja $F_{ij}$ o instante em que o job $j$ é finalizado na máquina $i$.
Podemos definir o \textit{sum finishing time} como a soma dos instantes em que cada job é finalizado na máquina 2: \\
\[f = \sum_{j=1}^{n} F_{2j}\] \\
Assim, o problema de sum-finishing-time (SFTP) é o problema de determinar a ordem em que devem ser
processadas as tarefas de forma que $f$ seja mínimo.
Além disso, podemos considerar tal problema apenas como a decisão de uma permutação dos jobs, já que é possível
obter uma solução ótima para o SFTP na qual ambas as máquinas executam as tasks na mesma ordem, sem
necessidade de tempo de espera (ocioso) entre jobs \citep[p. 445]{Papadimitriou82}.


%\section{Estrutura do Relatório}


\section{Metodologia}
\subsection{Branch-and-Bound}

\subsubsection{Descrição}

O método de branch-and-bound é baseado na idéia de se enumerar todas as soluções viáveis
de um problema de otimização combinatória de forma inteligente. O \textit{branch} se refere
ao processo de partição do espaço da solução, e o \textit{bound} se refere a
\begin{inparaenum}[\itshape (i)]
    \item prevenir a geração de nós que não contém solução válida;
    \item e a utilizar limitantes superiores\footnote{upper bound} e inferiores\footnote{lower bound}
para evitar uma possível busca exaustiva
\end{inparaenum} \citep[p. 433]{Papadimitriou82}.
Vale ressaltar que tais
limitantes não influenciam o método na busca de uma solução ótima, já que eles são
utilizados apenas para evitar que nós comprovadamente improdutivos sejam explorados. \\

Existem também, como forma de eliminar nós que não compõem uma solução ótima, relações
de dominância, onde um nó com limite inferior que seja superior ao valor de uma solução
já encontrada pode ser simplesmente desconsiderado. Há ainda a possibilidade de um nó
qualquer ter decidido sobre as mesmas variáveis de um outro\footnote{ambos os nós gerariam exatamente
os mesmos descendentes} e ainda possuir
um valor parcial (da função objetivo) menor, dessa forma,
este pode ser desconsiderado por ser dominado pelo primeiro \citep[p. 442--443]{Papadimitriou82}.\\

Assim, é possível encontrar uma solução ótima exata para o problema dado de forma relativamente
eficiente, uma vez que boa parte da árvore será podada devido às restrições impostas, o que torna
o método de branch-and-bound uma boa abordagem para resolver problemas \textit{NP}-Completo.\\

Algumas observações importantes devem ser feitas em relação à modelagem do método branch-and-bound.
A ordem em que os nós são escolhidos para serem explorados podem seguir a ordem first-in-first-out
(fila), last-in-first-out (pilha) ou least-cost (fila de prioridade). Em termos de eficiência,
podemos dizer que se utilizarmos um algoritmo de branch-and-bound com critério least-cost,
uma função melhor para o cálculo de limite inferior\footnote{$\hat{c}_2$ é melhor que
$\hat{c}_1$ se $\hat{c}_1(X) \leq \hat{c}_2(X) \leq c(X)$ para todo nó $X$}
pode fazer com que o número total de nós gerados aumente \citep[p. 413]{Horowitz78},
ou seja, tal função não representaria um ganho no tempo de resolução do problema.
 

\subsubsection{Formulação}

\citet[p. 446--447]{Papadimitriou82} descreve um limite inferior bastante eficiente,
o qual transcrevemos a seguir. Considere um nó
arbitrário que escalona os jobs contidos no conjunto $M \subseteq \{1,\ldots,n\}$, onde $|M| = r$.
Seja $t_k$, $k=1,\ldots,n$, o índice do $k$-ésimo job no schedule\footnote{escalonamento} de qualqer descendente do nó em
questão. O custo desse schedule, o qual desejamos calcular o limite, é
\begin{equation} \label{eq:fm} f = \sum_{i \in M} F_{2i} + \sum_{i \not\in M} F_{2i} \end{equation}

Supondo que cada job pudesse iniciar sua execução na máquina 2 imediatamente após o seu término na
máquina 1, o segundo somatório na equação \eqref{eq:fm} seria
\[S_1 = \sum_{k=r+1}^{n} [F_{1t_r} + (n-k+1)\tau_{1t_k} + \tau_{2t_k}] \]

Se isso não for possível, $S_1$ pode apenas crescer, logo
\[\sum_{i \not\in M} F_{2i} \geq S_1\]

Analogamente, supondo que cada job pudesse iniciar sua execução na máquina 2 imediatamente
após o término do job anterior na máquina 2, o segundo somatório na equação \eqref{eq:fm} seria
\[S_2 = \sum_{k=r+1}^{n} [\max{(F_{2t_r},F_{1t_r}} + \min_{i \not\in M}{\tau_{1i}}) 
+ (n-k+1)\tau_{2t_k} ]\]

Novamente, esse é um limite inferior
\[\sum_{i \not\in M} F_{2i} \geq S_2\]

Portanto
\[f \geq \sum_{i \in M}{ F_{2i} + \max{(S_1, S_2)}}\]

Entretanto, esse limite depende de como os jobs restantes são escalonados, através de $t_k$.
Tal dependência pode ser eliminada se notarmos que $S_1$ é minimizado escolhendo-se $t_k$ de forma
que as tarefas de tamanho $\tau_{1t_k}$ estejam em ordem crescente, e que $S_2$ é
minimizado escolhendo-se
$t_k$ de forma que as tarefas de tamanho $\tau_{2t_k}$ estejam em ordem crescente. Sendo
os resultados mínimos $\hat{S}_1$ e $\hat{S}_2$, temos que
\begin{equation} \label{eq:lbound}
    f \geq \sum_{i \in M} F_{2i} + \max(\hat{S}_1, \hat{S}_2)
\end{equation}
é um limite inferior facilmente calculado. \\

Finalmente, \citet[p. 448]{Papadimitriou82} também descreve uma relação natural de dominância.
Suponha dois nós $t$ e $u$ que
representam escalonamentos parciais do mesmo conjunto de jobs, $M$.
Sejam $t_k$ e $u_k$ os $k$-ésimo
jobs escalonados sob o schedule parcial $t$ e $u$, respectivamente. Assim, se
\begin{equation} \label{eq:dom1}F_{2t_r} \leq F_{2u_r}\end{equation}
(ou seja, o conjunto de jobs $M$ não termina mais tarde na máquina 2 sob o schedule parcial $t$) e se
\begin{equation} \label{eq:dom2}\sum_{i \in M} F_{2i} |_{\text{schedule }t} \leq
    \sum_{i \in M} F_{2i} |_{\text{schedule } u} \end{equation}
então, a melhor solução possível para $t$ é pelo menos tão boa
quanto a melhor solução possível para $u$.
Portanto, as equações \eqref{eq:dom1} e \eqref{eq:dom2} definem uma relação de dominância de
$t$ sobre $u$, fazendo com que o nó $u$
possa ser removido da árvore sem que haja interferência na resolução do problema.

\subsubsection{Desenvolvimento}
A implementação do método branch-and-bound se deu seguindo as equações \eqref{eq:lbound},
\eqref{eq:dom1} e \eqref{eq:dom2}, sempre alterando o limite superior quando uma solução
melhor é encontrada. Há também a limitação de tempo de execução e número máximo de nós
explorados indicados pelo arquivo \textit{param}.\\

Para armazenar, em cada nó, os jobs que haviam sido escalonados e sua ordem, utilizamos
um vetor $v$ de permutação onde, para cada job $j$, o valor $v[j]$
indica sua posição no escalonamento.
Dessa forma, para gerar um novo nó a partir de seu pai, é necessário copiar
tal vetor ($\Theta(n)$) e inserir o novo job escolhido ($\Theta(1)$), além de calcular seu lower bound
($\Theta(n)$) dado pela equação \eqref{eq:lbound}. Logo, a geração de um novo nó gasta tempo
$\Theta(n) + \Theta(1) + \Theta(n) = \Theta(n)$.
Além disso, para verificar a dominância entre dois nós, é necessário conferir seus
valores $F_{2i}$ ($\Theta(1)$) e seus vetores de permutação ($O(n)$), o que leva tempo total
$\Theta(1) + O(n) = O(n)$.\\

Para a escolha dos nós a serem explorados, fizemos uma fila de prioridades de acordo
com o lower bound calculado, de tal forma que
a inserção e a remoção da fila gastam tempo $O(\log{p})$, onde $p$ é o total de nós ativos no
momento da operação. Sabe-se que o número máximo de nós ativos é dado pelo total de possíveis
folhas na árvore de busca ($p \leq n!$), de forma que essas operações gastem sempre
$O(\log{n!}) = O(n\log{n})$.
Finalmente, para a geração dos vetores de jobs ordenados, um por $\tau_{1j}$ e outro por
$\tau_{2j}$, utilizamos a função \textit{qsort} da própria biblioteca padrão (\textit{stdlib})
gastando $O(n^2)$ para cada. Apenas para obter um limite superior inicial, escalonamos os jobs
na ordem em que são passados e guardamos essa solução viável inicial.\\

Para informar o usuário do término do programa, é indicada a forma de finalização da execução,
podendo ser por encontrar uma solução ótima, por limite de tempo ou por limite de nós explorados.
Em seguida, são indicados o total de nós explorados, o tempo de execução e a melhor
solução encontrada (permutação de jobs) com seu respectivo sum-finishing-time. Além disso, são
impressos os valores primal\footnote{melhor solução encontrada} e
dual\footnote{menor lower bound entre os nós ativos}, e os respectivos tempos para calculá-los.
No caso do algoritmo gastar um tempo
considerável de execução, uma mensagem é impressa a cada minuto e tem o seguinte formato:\\[0.2cm]
\texttt{+ tempo: ttt \qquad (ppp; qqq) \qquad xxx}\\[0.2cm]
onde `\texttt{ttt}' é o tempo gasto (em segundos), `\texttt{ppp}' é o total de nós ativos,
`\texttt{qqq}' é o total de nós que já foram explorados e `\texttt{xxx}' é o valor
da melhor solução encontrada.
Todas as mensagens são impressas na saída padrão (\textit{stdout}).\\

Se a execução for encerrada por limite de tempo ou por limite de nós explorados, o primeiro nó
da fila de prioridades é removido, comparado com a melhor solução encontrada e aquele que tiver
o menor custo é retornado. No caso do nó em questão não ter um escalonamento completo, 
os jobs pendentes são selecionados de acordo com o menor valor de $\tau_{1j} + \tau_{2j}$
[Seção \ref{para:heur}, Primeira abordagem].




\subsection{Programação Linear Inteira}


\subsubsection{Descrição}

O método de Programação Linear Inteira (PLI) é, de forma similiar à Programação Linear,
descrito como um problema de otimização
com uma função objetivo a ser minimizada (ou maximizada) seguida de uma série de restrições
definidas através de combinações lineares das variáveis em questão,
incluindo ainda a integralidade destas. Ou seja, um problema PLI segue o formato
\[\begin{array}{c} \min c'x \\ Ax = b \\ x \in \mathbb{Z} \end{array}\]
Vale ressaltar que os parâmetros $A$, $b$ e $c$ também são inteiros
\citep[p. 307]{Horowitz78}. \\

Uma observação importante a ser feita é que, para se resolver um problema PLI,
não basta apenas resvolê-lo como um PL comum e então arredondar os valores encontrados.
Os arredondamentos podem gerar soluções subótimas ou ainda inviáveis, o que tornaria
tal aproximação um problema por si só, fazendo com que seja mais interessante resolver
o PLI de forma independente \citep[p. 307--308]{Papadimitriou82}.



\subsubsection{Formulação}

Para resolver o problema através de PLI, usamos os seguintes parâmetros
\begin{itemize}
    \item \begin{math}\mathcal{J} = \{J_1,\ldots,J_n\} \end{math} : conjunto de $n$ jobs
    \item $\tau_{ij}$ : tempo de processamento do job $j \ (1,\ldots,n)$ na máquina $i \ (1,2)$
    \item $T = \sum_{j=1}^{n} \sum_{i=1}^{2} \tau_{ij} $ : parâmetro auxiliar suficientemente grande
\end{itemize} 

Além disso, criamos as seguintes variáveis de decisão
\begin{itemize}
    \item $s_j$ : início de execução do job $j \ (1,\ldots,n)$ na máquina 1 
    \item $f_j$ : término de execução do job $j \ (1,\ldots,n)$ na máquina 2
    \item $\delta_{ik} = \begin{cases}
                            1 & \text{se o job $i$ é processado antes do job $k$} \\
                            0 & \text{caso contrário}
                           \end{cases}
          \qquad i \neq k, \quad i,k = 1,\ldots,n$
\end{itemize}

Dessa forma, para resolver o PLI enunciado anteriormente com os valores
descritos acima, foram construídas as restrições a seguir.
\begin{enumerate}
   \item Primeiramente, definimos as regras das variáveis de ordem $\delta_{ik}$
        de forma que reflitam o seu critério de atribuição
        \begin{align*}
             \delta_{ik} + \delta_{ki}& =1 & i < k,    & \quad i,k = 1,\ldots,n\\
             \delta_{ik}& \geq0            & i \neq k, & \quad i,k = 1,\ldots,n
        \end{align*}
            
        

    \item Em seguida, são definidas regras para o início de cada job de acordo
        com a ordem escolhida
        \begin{align*}
            \delta_{ik}*T + s_i& \geq s_k + \tau_{1k} & i \neq k, \quad & i,k=1,\ldots,n  \\
            s_i& \geq 0 &\quad& \ \ \  i=1,\ldots,n
        \end{align*}
        Temos que, se o job $i$ é processado antes do job $k$,
        então $\delta_{ik} = 1$ e, dessa forma,
        ocorre uma espécie de relaxação já que $T \geq s_k + \tau_{1k} - s_i$ é sempre verdade para
        qualquer $i,k = 1,\ldots,n$.
        Analogamente, se o job $i$ é processado depois do job $k$,
        então $\delta_{ik} = 0$ e, dessa forma,
        temos que $s_i \geq s_k + \tau_{1k}$,
        o que condiz com o significado da variável $\delta_{ik}$.

    \item Utilizando o raciocínio anterior, criamos as regras para o fim de cada job
        \begin{align*}        
            \delta_{ik}*T + f_i &\geq f_k + \tau_{2i} & i \neq k, & \quad i,k=1,\ldots,n \\
            f_i &\geq 0 && \quad \ \ \  i=1,\ldots,n
        \end{align*}
        Temos que, se o job $i$ é processado antes do job $k$,
        então $\delta_{ik} = 1$ e, dessa forma,
        ocorre uma espécie de relaxação já que $T \geq f_k + \tau_{2i} - f_i$ é sempre verdade para
        qualquer $i,k = 1,\ldots,n$.
        Analogamente, se o job $i$ é processado depois do job $k$,
        então $\delta_{ik} = 0$ e, dessa forma,
        temos que $f_i \geq f_k + \tau_{2i}$,
        o que condiz com o significado da variável $\delta_{ik}$. \\

        E, seguindo a definição do problema, deve ser criada uma regra para o funcionamento da
        execução de cada job
        \begin{align*} f_i &\geq s_i + \tau_{1i} + \tau_{2i} && \quad i=1,\ldots,n   \end{align*}

\end{enumerate}

Assim, obtemos um total de $n+n+2\cdot\binom{n}{2} = n^2+n$ variáveis
e, se desconsiderarmos a não-negatividade das variáveis,
há um total de
$\binom{n}{2} +2\cdot\binom{n}{2} + 2\cdot\binom{n}{2} + n=
(5n^2 - 3n)/2$ restrições.
Finalmente, temos que a função objetivo a ser calculada é dada por
\[ \text{\textbf{minimizar }} sft = \sum_{j=1}^{n} f_j \]


\subsubsection{Desenvolvimento}
A implementação do método PLI se deu pelo desenvolvimento de um programa que faz
a leitura da entrada, gera os arquivos no formato \textit{GNU MathProg},
executa o
resolvedor do pacote \texttt{glpk} (\textit{gplsol}) e realiza a leitura dos arquivos
gerados na saída pelo utilitário. Os arquivos gerados podem ser visualizados se a constante
\textsl{DELETE\_PLI\_FILES} for $0$; eles possuem nome no formato \textsl{\_SFTP\_PLI} seguidos
de sua respectiva extensão, as quais são descritas a seguir.\\
\begin{listliketab}
\storestyleof{itemize}
\begin{tabular}{Llll}
    $\diamond$ &\textbf{mod}  &\textbf{--}& modelagem PLI do problema no
            formato \textit{GNU MathProg}\\
    $\diamond$ &\textbf{dat}  &\textbf{--}& dados lidos da entrada e convertidos
            para o formato \textit{GNU MathProg}\\
    $\diamond$ &\textbf{sol}  &\textbf{--}& solução encontrada para a instância fornecida\\
    $\diamond$ &\textbf{disp} &\textbf{--}& saída formatada para
            facilitar o cálculo da permutação\\
    $\diamond$ &\textbf{log}  &\textbf{--}& cópia da saída do utilitário resolvedor
\end{tabular}
\end{listliketab}

Após a geração de tais arquivos, o comando utilizado para resolver o PLI é impresso
na saída de erro (\textit{stderr}) e, em seguida, é apresentada toda a saída do
utilitário \texttt{glpk} na saída padrão (\textit{stdout}).
A partir da linha ``\textit{Integer optimization begins\ldots}'' é possível acompanhar o
processamento do resolvedor, através das impressões realizadas na saída padrão
a cada 5 segundos, que
seguem o formato a seguir \citep[p. 72]{glpkman}:\\[0.2cm]
\texttt{+nnn: mip = xxx >= yyy\quad gap (ppp; qqq)}\\[0.2cm]
onde `\texttt{nnn}' é o numero da iteração do simplex, `\texttt{xxx}' é o valor da melhor
solução encontrada (em notação científica), `\texttt{yyy}' é o valor mínimo
para qualquer solução ótima (em notação científica), `\texttt{gap}' é o intervalo relativo
calculado como $gap = |xxx - yyy|/(|xxx| + \epsilon)\cdot100\%$, `\texttt{ppp}' é o
total de nós ativos e `\texttt{qqq}' é o total de nós que já foram explorados e, portanto,
removidos da árvore de busca. \\

Ao término da execução do resolvedor, pode-se conferir o tempo gasto e o total de nós explorados.
Então, o programa imprime, na saída padrão, a melhor solução encontrada (permutação de jobs)
com seu respectivo sum-finishing-time. Uma observação importante a ser feita é o fato
do \texttt{glpk} não permitir limitação no total de nós a serem explorados, mas apenas
no total de memória utilizada. Assim, realizamos uma aproximação desses valores através
de uma constante nomeada \textsl{MB\_PER\_NODE}, que é um palpite para o espaço
(em \textit{megabytes}) utilizado por cada nó.




\subsection{Heurística}
\subsubsection{Descrição}
O método de heurística se fundamenta na idéia de resolver um problema de forma eficiente,
com o intuito de encontrar soluções rapidamente.
Para que isso seja possível, é preciso relaxar a idéia de se resolver um problema, de forma que
o requisito de encontrar uma solução ótima seja substituído por outro, onde é necessário apenas
encontrar uma solução viável que seja \textsl{próxima} à ótima \citep[p. 560]{Horowitz78}.\\

Assim, é notável que, para tal metodologia, não existe qualquer
garantia de que a solução encontrada seja ótima. Mais ainda,
também não há certeza na qualidade da resposta, de forma que tal método possa encontrar
soluções potencialmente ruins.
Apesar das deficiências, o que torna a herística uma boa alternativa é
justamente a velocidade, uma vez que, removendo-se a necessidade de otimalidade, é possível
encontrar boas soluções para problemas \textit{NP}-Completo em tempo polinomial.\\

Para determinar a qualidade de um algoritmo de tal natureza, pode-se
apenas testá-lo exaustivamente, a ponto de ser possível afirmar que ele seja
 \textsl{probabilisticamente bom}, ou seja, dada uma instância
aleatória $I$, existe uma grande chance do algoritmo encontrar uma boa solução, ou mesmo
uma solução ótima \citep[p. 596]{Horowitz78}.



\subsubsection{Formulação}
\label{para:heur}
Para a construção de uma heurística para o problema, foram idealizadas
algumas possibilidades, de forma
que a resolução escolhida fosse a melhor.
As quatro abordagens descritas a seguir seguem um padrão
fortemente guloso, com idéias bastante intuitivas, simples e práticas.

\paragraph{Primeira abordagem}
Levando em conta a idéia de minimizar o instante de término
de cada serviço, definimos o tempo total de processamento 
$T_j = \tau_{1j}+\tau_{2j}$ para cada job $j = 1,\ldots,n$. Assim,
ordenamos os jobs em ordem não-decrescente de tempo de processamento
utilizando a função \textit{qsort} ($O(n^2)$)
e calculamos o sum-finishing-time da permutação obtida ($\Theta(n)$),
consumindo tempo total $O(n^2) + \Theta(n) = O(n^2)$
[Algoritmo \ref{alg:tt}].


\paragraph{Segunda abordagem}
Resolvemos um problema similar ao SFTP,
mas que é possível encontrar uma solução ótima em tempo polinomial.
Tal problema $P'$ consiste em finalizar todos os jobs no menor tempo possível,
ou seja, temos que a função a ser minimizada é dada por
$f' = \max_{1 \leq j \leq n}{F_{2j}}$.\\

\citet{Johnson54} [Algoritmo \ref{alg:john}]
descreve um algoritmo polinomial para este problema,
o qual explicamos a seguir. Primeiramente, particiona-se o conjunto
$\mathcal{J}$ em dois conjuntos $L_1$ e $L_2$, onde
$L_1 = \{j|\tau_{1j} < \tau_{2j}\}$ e
$L_2 = \{j|\tau_{1j} \geq \tau_{2j}\}$.
Em seguida, ordena-se $L_1$ em ordem não-decrescente de $\tau_{1j}$ e
$L_2$ em ordem não-crescente de $\tau_{2j}$.
A sequência ótima consiste nos jobs ordenados em $L_1$ seguido dos jobs
ordenados em $L_2$.\\


Dessa forma, resolvemos o problema fazendo a partição do jobs
($\Theta(n)$) e ordenando cada partição através da função
\textit{qsort} ($O(n^2)$). Por fim, bastou calcular o sum-finishing-time da permutação
encontrada ($\Theta(n)$), o que gastou tempo total
$\Theta(n) + O(n^2) + \Theta(n) = O(n^2)$.


\paragraph{Terceira abordagem}
Utilizamos um algoritmo simples de busca local,
chamado de \textsl{Hill-climbing} em \citet[p. 111]{Russell03} [Algoritmo \ref{alg:hc}]
e descrito como ``uma tentativa
de encontrar o topo do Monte Everest em uma neblina densa e sofrendo de amnésia''.\\

Definimos um vizinho de um estado como a permutação de apenas dois jobs $i$ e $k$, 
$i \neq k$, $i,k = 1,\ldots,n$, 
de forma que cada estado possui $\binom{n}{2} = (n^2-n)/2$ vizinhos. Assim, para determinar
cada vizinho gasta-se $\Theta(1)$, totalizando $\Theta(1) \cdot \Theta(n^2) = \Theta(n^2)$
para todas as possíves permutações e, para calcular o custo (sum-finishing-time) de cada uma,
gasta-se $\Theta(n)$. Logo, o tempo para determinar o estado seguinte de cada iteração é
$\Theta(n^2) \cdot \Theta(n) = \Theta(n^3)$.\\

Como estado inicial, escolhemos o melhor entre as soluções encontradas pelas abordagens descritas
anteriormente.
Vale ressaltar que o número total de iterações executadas até que se encontre algum mínimo local é
potencialmente o total de permutações possíveis entre os jobs, fazendo com que o algoritmo
tenha tempo $O(n^2) + O(n^2) + O(n!) \cdot \Theta(n^3) = O(n^n)$,
mas, felizmente, o que se verifica na prática é uma execução bastante rápida.


\paragraph{Quarta abordagem}
Aproveitando o algoritmo de busca local produzido,  implementamos o
\textsl{Greedy Randomized Adaptive Search Procedure} \citep{Feo95}
[Algoritmo \ref{alg:grasp}].
Basicamente, a idéia é gerar estados iniciais aleatórios e aplicar a busca local
em cada um, anotando sempre a melhor solução encontrada.\\

Para a geração de permutações randômicas no conjunto de jobs, utilizamos o algoritmo
descrito em \cite[p. 102--104]{Cormen01} [Algoritmo \ref{alg:rand}],
gastando $\Theta(n)$ em cada chamada.
O total de iterações escolhido foi $n^3$, fazendo com que o programa
finalizado utilize tempo total $(\Theta(n) + O(n^n)) \cdot \Theta(n^3) = O(n^n)$.
Na prática, apesar de ter a mesma complexidade do \textsl{Hill-climbing},
o \textsl{GRASP} acaba consumindo um tempo consideravelmente maior,
já que utiliza a busca local diversas vezes.


\subsubsection{Desenvolvimento}
Tratando-se de algoritmos simples, a implementação do método de heurística
se deu de maneira direta. Apenas um programa foi produzido contendo as quatro abordagens
anteriores, o qual retorna para o usuário o tempo total de execução,
seguido da melhor solução encontrada (permutação de jobs)
e seu respectivo sum-finishing-time; tal programa tem complexidade
$O(n^2) + O(n^2) + O(n^n) + O(n^n) = O(n^n)$.

\input{extra/algoritmo}

\section{Discussão}

\subsection{Dados}
Executamos as instâncias de teste fornecidas nos três programas desenvolvidos, coletando 
as saídas geradas. Todas as instâncias de teste foram executadas com limite máximo de $10^9$ 
nós explorados e tempo máximo de execução de uma hora (3600 segundos).
A máquina utilizada foi um Core 2 
Quad Q8400, 2.66 GHz, com 3.8GB de memória RAM. \\

Anotamos, para os algoritmos de Branch-and-Bound e PLI, o total de nós gerados, os valores 
primal e dual finais, além do instante em que foram calculados. O limitante dual do método
branch-and-bound foi obtido pelo menor valor de lower bound entre os nós ativos.
Para a Heurística, registramos 
o tempo de execução, o valor encontrado e a distância 
relativa aproximada $\hat{d}$, explicada a seguir.\\

Seja $I$ uma instância aleatória, temos que a distância relativa $d$
entre uma solução ótima $F^{*}(I)$
e a solução gerada pela heurística $\hat{F}_{heur}(I)$ é dada por
\[d = \frac{|F^{*}(I) - \hat{F}_{heur}(I)|}{F^{*}(I)} \cdot 100\%\]
Considerando que nem sempre podemos ter uma solução ótima devido às limitações de tempo,
adaptamos o valor $F^{*}(I)$
para a melhor solução encontrada entre os métodos de branch-and-bound ($F^{bnb}(I)$)
e PLI ($F^{pli}(I)$) fazendo
\[ F^{\#}(I) = \min(\hat{F}_{bnb}(I), \hat{F}_{pli}(I)) \]
Assim, temos uma nova distância relativa aproximada $\hat{d}$ dada por
\[\hat{d} = \frac{\hat{F}_{heur}(I) - F^{\#}(I)}{F^{\#}(I)} \cdot 100\%\]
onde um resultado negativo indica que a heurística encontrou uma solução
melhor que os outros métodos.\\

A Tabela \ref{tab:dados} contém os dados coletados. Os tempos estão todos em segundos
e a distância está em porcentagem. A marcação (*) indica que o teste foi interrompido
por limitação de tempo; nenhum teste ultrapassou o limite
de nós explorados. O PLI não conseguiu encontrar uma solução viável para as instâncias 
\textsl{i27} e \textsl{i29} no tempo estipulado.

\begin{sidewaystable}[h]
\centering
\caption{Dados obtidos nos testes\label{tab:dados}}
\input{extra/tabela}
\end{sidewaystable}

\clearpage

Com os dados obtidos, montamos o gráfico indicado pela Figura \ref{graf:sftinst}.

\begin{figure}[htb]
\begin{center}
\caption{Gráfico SFT$\times$Instância\label{graf:sftinst}}
\includegraphics[width=\textwidth]{extra/grafico.png}
\end{center}
\end{figure}

\subsection{Análise}
Pela Tabela \ref{tab:dados} nota-se que, conforme o tamanho da instância aumenta,
diminui a quantidade de nós explorados. Isso ocorre pois, com mais jobs a serem escalonados,
mais tempo é gasto na geração de nós filhos, na armazenagem e na comparação
com os nós ativos, fazendo com que o total de nós efetivamente explorados seja menor,
tanto para branch-and-bound quando para PLI.
Percebe-se também a notada diferença entre a eficiência dos métodos utilizados.
Enquanto o PLI obteve o pior desempenho, gerando soluções frequentemente ruins, o branch-and-bound
acabou sendo relativamente bom, considerando o tamanho das instâncias testadas e o fato
de ser um algoritmo exato.\\

Sendo PLI um caso particular de branch-and-bound \citep[p. 433--438]{Papadimitriou82}, fica clara a
impossibilidade desse método de utilizar toda a flexibilidade que é possível se obter no outro,
como as podas por inviabilidade ou limitantes, além de regras de dominância, exploração
de nós mais promissores,
entre outros. Isso tornaria PLI um método menos interessante, não fosse a relativa simplicidade
em se obter uma formulação, visto às complexidades embutidas nos cálculos de lower bounds,
verificação de dominância e todas as outras especificidades da abordagem por branch-and-bound.\\

Surpreendente foi o fato da Heurística encontrar soluções muito boas,
diversas vezes melhores até que os métodos exatos, e, para isso, gastar um tempo
bastante pequeno.
A critério de comparação, em apenas um caso de teste a Heurística obteve uma solução pior
que os outros métodos e a sua distância média ficou em $-$2,5$\%$. Tratando-se de heurística,
vale ressaltar que a terceira abordagem obteve soluções gastando sempre apenas um segundo
de execução e, mesmo assim, atingiu uma distância média de $-$2,1$\%$, o que podemos
caracterizar como o \textit{tradeoff} entre o custo de se calcular uma heurística melhor
e seu tempo de processamento.\\


\subsection{Conclusão}

Visto a dificuldade em se resolver problemas $NP$-Completo e a quantidade de problemas 
que se encaixam nesta classe, a necessidade das aplicações em obter uma boa solução rapidamente
valorizam as técnicas de tratamento de problemas $NP$-Completo. \\

O algoritmo de Branch-and-Bound apresentou melhor desempenho do que PLI, no entanto, a elaboração
é mais trabalhosa, exigindo conhecimento mais detalhado sobre o problema. 
É necessário saber como gerar (branch) e armazenar os nós filhos, assim como saber calcular bons
limitantes para as podas (bound).
Por outro lado, qualquer problema modelado corretamente como PLI pode ser solucionado por um resolvedor PLI genérico,
assim, os esforços de desenvolvimento são menores, mas o desempenho obtido pode não ser o suficiente para a aplicação. \\ 

A Heuristica mostrou-se uma ótima abordagem na resolucao de problemas intratáveis, encontrando
soluções em tempo bastante pequeno, no entanto, sem garantias sobre a qualidade destas.
Considerando que os dados fornecidos por uma instância geralmente
são conhecidos apenas em valores aproximados, uma solução
aproximada não faz menos sentido que uma solução exata \citep[p. 560]{Horowitz78} \\

Desta forma, é importante que cada caso seja analisado, dadas suas especifidades, requisitos de desempenho e esforços 
de desenvolvimento, utilizando-se sempre da metodologia mais interessante.\\

O conhecimento adquirido no desenvolvimento deste trabalho é de grande
valia, já que pudemos implementar, colocar em prática e visualizar
alguns tópicos que tínhamos apenas uma idéia de como funcionavam, o que nos
fez firmar o aprendizado de uma forma muito melhor. $\square$


\bibliography{extra/bibliografia}{}
\bibliographystyle{plainnat}


\end{document}

